package zcw.com.lib_leet_code;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/21.<br><br>
 *
 * 二叉树的最近公共祖先
 */
public class Topic236 {

    public static void main(String[] args) {
        Topic236 instance = new Topic236();

        List<Integer> list = Arrays.asList(3,5,1,6,2,0,8,null,null,7,4);
        TreeNode root = Util.createTree(list);
        TreeNode nodeP = Util.getNode(root, 5);
        TreeNode nodeQ = Util.getNode(root, 1);
        System.out.println(instance.lowestCommonAncestor(root, nodeP, nodeQ).val);

        nodeQ = Util.getNode(root, 4);
        System.out.println(instance.lowestCommonAncestor(root, nodeP, nodeQ).val);

        list = Arrays.asList(1,2);
        root = Util.createTree(list);
        nodeP = Util.getNode(root, 1);
        nodeQ = Util.getNode(root, 2);
        System.out.println(instance.lowestCommonAncestor(root, nodeP, nodeQ).val);


    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> map = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();

        map.put(root, null);
        queue.offer(root);

        while (!map.containsKey(p) || !map.containsKey(q)) {
            TreeNode node = queue.poll();
            if(node != null) {
                map.put(node.left, node);
                map.put(node.right, node);
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }

        Set<TreeNode> set = new HashSet<>();
        TreeNode temp = p;
        while (temp != null) {
            set.add(temp);
            temp = map.get(temp);
        }

        temp = q;
        while (!set.contains(temp)) {
            temp = map.get(temp);
        }

        return temp;
    }

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor2(root.left, p, q);
        TreeNode right = lowestCommonAncestor2(root.right, p, q);

        if(left == null && right == null)   return null;
        if(left != null && right != null)   return root;
        return left == null ? right : left;
    }
}
